package DataStructure.tree;

/**
 * 654. 最大二叉树 https://leetcode.cn/problems/maximum-binary-tree
 * 题目简述：给定一个不重复的整数数组nums，构建一棵二叉树：根节点为数组最大值，左右子树分别由最大值左边数组和右边数组获取最大值递归的构造
 */
public class ConstructMaximumBinaryTree {

    /**
     * 思路：递归。给定一段数组，获取其最大值节点，获取其左半数组中最大值节点作为左孩子，获取其右半数组中最大值节点作为右孩子，最后返回该节点
     */
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return traversal(nums, 0, nums.length-1);
    }

    public TreeNode traversal(int[] nums, int low, int high) {
        if(low > high) return null;
        int max = nums[low];
        int p = low;
        for(int i=low+1;i <= high;i++) {
            if(nums[i] > max) {
                max=nums[i];
                p=i;
            }
        }
        TreeNode node = new TreeNode(max);
        node.left = traversal(nums, low, p-1);
        node.right = traversal(nums, p+1, high);
        return node;
    }
}
